class Solution {//leetcode416——分割等和子集
public:
    bool canPartition(vector<int>& nums) {
        int sum=0,n=nums.size();
        for(auto e:nums){
            sum+=e;
        }
        if(sum%2!=0) return false;

        sum/=2;
        vector<bool> dp(sum+1,false);
        dp[0]=true;
        for(int i=1;i<n+1;i++){
            for(int j=sum;j>=1;j--){
                dp[j]=dp[j];
                if(j-nums[i-1]>=0) dp[j]=dp[j]||dp[j-nums[i-1]];
            }
        }
        return dp[sum];
    }
};